\section{АЛГОРИТМЫ ПОСТРОЕНИЯ И \\
РАСПОЗНАВАНИЯ ДВУМЕРНЫХ ШТРИХКОДОВ}

\subsection{\textsc{Коды Рида--Соломона}}
\label{sec:RSCode}

Коды Рида--Соломона позволяют производить коррекцию и выявление ошибок 
в любой последовательности байт. Наиболее важным свойством этого метода
является возможность исправить $k$ и выявить $2k$ ошибок при дополнении
сообщения $2k$ дополнительными символами. Другими словами, число
максимально исправляемых ошибок вдвое меньше добавленных символов, а 
выявляемых~--- совпадает с числом дополнительных символов. Этот метод
используется практически во всех матричных кодах\cite{bib:RSCode}. 

Коды Рида--Соломона, или РС-коды, относятся к недвоичным циклическим кодам, 
т. е. кодам, символы которых взяты из конечного поля, содержащего $q > 2$ 
элементов и обозначаемого $GF(q)$, где $q$ --- степень некоторого 
простого числа.

Пусть необходимо передать по каналу связи последовательность из $M$ двоичных 
элементов. Разобьем эту последовательность на блоки по $m$ элементов и обозначим 
их через некоторые символы $b_0, b_1, b_2, ..., b_{N-1}$, где $N = \frac{M}{m}$. 
Полное число различных значений $m$-элементных блоков равно $q=2^m$. Таким 
образом, передаваемая последовательность представляется в виде некоторой 
$q$-ичной последовательности: $b_0, b_1, ..., b_{N-1}$. 

Некоторая совокупность $q$-ичных последовательностей образует $q$-ичный код. 
Такие коды, как и двоичные коды, могут быть простыми и помехоустойчивыми.
Кодовые комбинации $q$-ичного кода могут быть представлены в виде многочленов 
с $q$-ичными коэффициентами --- элементами поля $GF(q)$. При этом $q$-ичные 
коэффициенты как элементы поля $GF(q)$ являются в рассмотренном примере 
многочленами с двоичными коэффициентами. Например:

$$B(x)= b_0(z)x^0 + b_1(z)x^1 + ... + b_{N-1}(z)x^{N-1},$$
где: $b_i(z) = b_0z^0 + b_1z^1 + ... + b_{m-1}z^{m-1}$.
Здесь $b_i \in \{0,1\}$, а $z$ --- формальная переменная многочлена 
с двоичными коэффициентами.

\subsubsection{Определение кодов Рида--Соломона}
Кодом Рида--Соломона (РС-кодом) называют циклический $(N,K)$-код, при 
$N = q-1$, множество кодовых комбинаций которого представляется многочленами 
степени $N-1$ и менее с коэффициентами из поля $GF(q)$, где $q > 2$ и 
является степенью простого числа, а корнями порождающего многочлена являются 
$N-K$ последовательных степеней: $a, a^2, a^3, ..., a^{D-1}$, некоторого 
элемента $a \in GF(q)$, где $D$ --- минимальное кодовое расстояние 
$(N,K)$-кода.

Из определения вытекает, что РС-код является подклассом БЧХ-кодов с 
$m_0 = 1$ \cite{bib:piterson}. Обычно считают элемент $a$ примитивным 
элементом поля $GF(q)$, т. е. все степени $a$ от $1$-й до $(q-1)$-й 
являются всеми различными ненулевыми элементами поля $GF(q)$. Порождающий 
многочлен РС-кода имеет степень $N-K = D-1$ и по теореме Безу может быть 
найден в виде произведения

$$g(x) = \prod_{i=1}^{D-1}(x-a^i)$$

В соответствии с теорией циклических кодов, порождающий многочлен $g(x)$ 
является делителем $x_{N-1}$ над $GF(q)$. Таким образом, РС-код над полем 
$GF(q)$ имеет длину кодовой комбинации $N = q-1$, число избыточных элементов 
в ней $N-K = D-1$ и минимальное кодовое расстояние $D = N-K+1$. Коды с 
подобным значением минимального кодового расстояния в теории кодирования 
получили название максимальных. При фиксированных $N$ и $K$ не существует 
кода, у которого минимальное кодовое расстояние больше, чем у РС-кода. 
Этот факт часто является веским основанием для использования РС-кодов. В 
то же время РС-коды всегда оказываются короче всех других циклических 
кодов над тем же алфавитом. РС-коды длины $N < q-1$ называют укороченными, 
а коды длины $q$ (или $q+1$) --- расширенными (удлинёнными) на один (или 
два) символа. В РС-коде может быть выбрано и другое значение $m_0$, если 
это оправдано.

\subsubsection{Исправление ошибок}

Начнём рассмотрение с процедуры декодирования с исправлением ошибок, 
известной как алгоритм Форни. 

Пусть в приёмник аппаратуры передачи данных (АПД) поступила кодовая 
комбинация РС-кода
$$C(x) = f(x) + e(x),$$
где $f(x)$~--- переданная передатчиком АПД кодовая комбинация, в которой 
в процессе передачи по каналу связи произошло $\upsilon$ ошибок, отображаемых 
многочленом $e(x)$ степени $\upsilon$. Каждый ненулевой компонент $e(x)$ 
описывается парой элементов: $Y_i$~--- величина ошибок и $X_i$~--- номер 
позиции ошибки (локатор ошибки). $Y_i$, $X_i$~--- элементы $GF(q)$.

Для описания ошибок используются:

1. Многочлен локаторов ошибок:
$$\Lambda(x)=
\prod_{i=1}^\upsilon (1 - x X_i) = 
\Lambda_\upsilon x^\upsilon + \Lambda_{\upsilon-1} x^{\upsilon - 1} +
... + \Lambda_1 x + \Lambda_0,$$
имеющих корни  $X_i^{-1}, i = 1, ..., \upsilon$, взаимные к локаторам 
ошибок, т. е. $X_i^{-1} a_i = 1$.

2. Многочлен значений ошибок $\Omega(x)$:
\begin{equation}
\Omega(x) =  S(x)\Lambda(x)\pmod {x^{2t}},
\label{eq:rs1}
\end{equation}
где 
$S(x)=\sum_{j=1}^{2t}S_{j}x^j=
\sum_{j=1}^{2t}\sum_{i=1}^\upsilon Y_iX_i^jx^j$~---
синдромный многочлен бесконечной степени, для которого 
известны только $2t$ коэффициентов для поступившей 
комбинации РС-кода. Здесь
$S_j=\sum_{i=1}^\upsilon Y_iX_i^j=e(a^j)$~---
элемент синдрома, $a^j$ --- корень порождающего многочлена РС-кода. 
Значения $S_j =  e(a^j)$ задаются проверками:
$$S_j = C(a^j) = f(a^j) + e(a^j) = e(a^j).$$

Равенство (\ref{eq:rs1}) определяет множество из ($2t-\upsilon$) уравнений и 
называется ключевым уравнением, так как оно представляется <<ключом>> 
решения задачи декодирования. Это становится понятным, если учесть, 
что степень $\Omega(x)$ не превышает $\upsilon-1$ и поэтому справедливо:
$$
[\Lambda(x)S(x)]_\upsilon^{2t-1}=0,
$$
где 
$[a(x)]_m^n = a_mx^m + a_{m+1}x^{m+1}+...+a_n x^n$.
Из (\ref{eq:rs1}) необходимо получить $\upsilon$ уравнений для $\upsilon$ неизвестных 
коэффициентов $L_k$. Эти уравнения являются линейными. Они могут 
быть решены обычными методами либо с помощью итерационных процедур. 
После нахождения многочлена $\Lambda$ ключевое уравнение позволяет 
найти неизвестные компоненты вектора $e(x)$ и по ним выходной вектор 
декодера: $f(x)= C(x) + e(x)$.

Простейшим путём нахождения корней многочлена $\Lambda$ является метод 
проб и ошибок, известный как процедура Ченя. Эта процедура состоит 
в последовательном вычислении $\Lambda(a^j)$ для каждого $j$ и проверки 
полученных значений на нуль. Если величина $L(a^{-k})$ равна нулю, 
то $a^k$ является взаимным к корню многочлена локаторов ошибок и 
$k$-й элемент кодовой комбинации содержит ошибку. Наиболее простым 
способом вычисления значения $\Lambda$ в точке $b$ является схема Горнера:
$$
\Lambda(b) = (...((( \Lambda_\upsilon b + \Lambda_{\upsilon-1})b + \Lambda_{\upsilon-2})b +
 \Lambda_{\upsilon-3})b + ... + \Lambda_0 ).
$$
Для вычисления $\Lambda(b)$ по схеме Горнера требуется только $u$ умножений 
и $\upsilon$ сложений, где $\upsilon$ --- степень $\Lambda$.
После определения локаторов ошибок с помощью ключевого уравнения 
находим значения ошибок. Для этого, используя значения сомножителей, 
входящих в равенство для $\Omega(x)$, перепишем ключевое уравнение следующим образом:
\begin{multline*}
\Omega(x) =
\left[\sum_{j=1}^{2t}\sum_{i=1}^\upsilon Y_iX_i^jx^{j-1}\right]
    \left[\prod_{i=1}^\upsilon (1 - x X_i)\right] \pmod{x^{2t}} = \\
=\sum_{i=1}^\upsilon Y_iX_i\left[(1 - x X_i)\sum_{j=1}^{2t}(X_ix)^{j-1}\right]
    \prod_{l \neq i}(1 - X_l x) \pmod{x^{2t}}.
\end{multline*}
Сворачивая выражение в квадратных скобках, получаем окончательно
$$
\Omega(x) =
\sum_{i=1}^\upsilon Y_iX_i(1-X_i^{2t} x^{2t})
    \prod_{l \neq i}(1 - X_l x) \pmod{x^{2t}}.
$$
Приводя это выражение по модулю $x^{2t}$, получаем
$$
\Omega(x) =
\sum_{i=1}^\upsilon Y_iX_i
    \prod_{l \neq i}(1 - X_l x).
$$

Вычислим многочлен значений ошибок на позиции $l$: $x = X_l^{-1}$
$$
\Omega( X_l^{-1}) =
\sum_{i=1}^\upsilon Y_lX_l
    \prod_{l \neq j}(1 - X_j  X_l^{-1}),
$$
откуда
$$
Y_l = \frac{\Omega( X_l^{-1})X_l^{-1}}{\prod_{l \neq j}(1 - X_j  X_l^{-1})}.
$$

Найдем производную от многочлена локаторов ошибок $\Lambda$:
$$
\Lambda^\prime(x) = - \sum_{i=1}^\upsilon Y_i{\prod_{l \neq j}(1 - X_j  X_l^{-1})}.
$$
Для l-й позиции получаем:
$$
\Lambda^\prime(X_l^{-1}) = -  X_l{\prod_{l \neq j}(1 - X_j  X_l^{-1})}.
$$

С учетом последнего выражения $Y_l$ значение ошибки на позиции 
$l$ принимает вид:
$$
Y_l = -\frac{\Omega( X_l^{-1})}{\Lambda^\prime(X_l^{-1})}.
$$
Данный способ вычисления значения ошибки известен в литературе 
как алгоритм Форни. 
Он позволяет найти значение ошибок по известным многочленам локаторов 
и значений ошибок.
Указанные многочлены вычисляются в результате решения ключевого уравнения.

\subsubsection{Алгоритм Берлекэмпа--Месси решения ключевого уравнения}

Нахождение решения ключевого уравнения, имеющего минимальную степень, 
эквивалентно построению регистра сдвига минимальной длины с обратными связями, 
отображающими $\Lambda$, порождающим первые $2t$ членов $S(x)$. Основное содержание 
алгоритма Берлекэмпа--Месси формулируется следующим образом. Вначале 
находят самый короткий регистр сдвига, генерирующий $S_1$. Далее проверяют, 
порождает ли этот регистр также $S_2$. Если порождает, то данный регистр 
по-прежнему остаётся наилучшим решением, и нужно проверить, порождает ли 
он следующие символы синдромного многочлена. На каком-то шаге очередной 
символ уже не будет генерироваться. В этот момент нужно изменить регистр 
таким образом, чтобы он:

1. правильно предсказывал следующий символ,

2. не менял предсказание предыдущих символов,

3. увеличивал длину регистра на минимально возможную величину.

Процесс вычисления продолжается до тех пор, пока не будут порождены первые 
$2t$ символов синдрома.

Алгоритм строится на основе итеративной процедуры. При каждой итерации 
должны сохраняться как многочлен связей $\Lambda$, так и добавка $B(x)$. 
Для каждого нового члена $S(x)$ предусматривается проверка правильности 
предсказания этого символа текущим многочленом связи. Если предсказание 
правильно, то многочлен связей не меняется, а добавка умножается на $x$. 
Если предсказание неправильно (невязка $\Delta r \neq 0$), то изменяют 
текущий многочлен связей, прибавляя к нему добавку. После этого проверяют, 
увеличилась ли длина регистра. Если она не увеличилась, то текущую 
добавку оставляют. Если длина регистра возрастает, то лучшей добавкой 
считают предыдущий многочлен связей. Для недвоичных полей добавку нормируют, 
чтобы невязка стала равной 1. Далее при каждом исправлении эту нормализованную 
добавку умножают на значение текущей невязки.

Блок-схема алгоритма Берлекэмпа--Месси приведена на рисунке 
\ref{fig:BMDiagram}. Процедура декодирования кодов Рида--Соломона, с 
исправлением ошибок, получившая название быстрого декодирования, 
представлена на рисунке \ref{fig:fastRS}. Для исправления ошибок 
декодер выполняет последовательность вычислений, реализующих 
алгоритм Берлекэмпа--Месси и алгоритм Форни. Алгоритм выполняется за 
$2t =  n - k$ итераций. При этом многочлен значений ошибок находится 
непосредственным умножением по формуле ключевого уравнения (\ref{eq:rs1}).

\begin{figure}[htb]
\centering
\includegraphics[scale=0.7]{img/BMDiagram}
\caption{Алгоритм Берлекэмпа--Месси}
\label{fig:BMDiagram}
\end{figure}

\begin{figure}[htb]
\centering
\includegraphics[scale=0.7]{img/fastRS}
\caption{Быстрое декодирование РС-кодов}
\label{fig:fastRS}
\end{figure}

Обозначения на рисунке \ref{fig:BMDiagram}:

$r$ --- номер итерации, $r = 0, 1, 2, ..., n - k =  2t$;

$S_r$ --- компонент синдрома;

$\Delta_r$ --- ошибка в вычислении $S_r$($r$-я невязка);

$\Lambda$ --- многочлен локаторов ошибок, в соответствии с компонентами которого 
строится регистр сдвига минимальной длины;

$L$ --- длина регистра сдвига;

$B(x)$ --- нормирующая добавка;

$\Omega(x)$ --- многочлен значений ошибок.

Поскольку $\Omega(x)$ находится умножением $\Lambda$ на $S(x)$, можно задать 
последовательность многочленов $\Omega_r(x)$, удовлетворяющих тем же рекуррентным 
соотношениям, что и многочлены $L_r(x)$. Чтобы избежать путаницы, обозначим 
добавку при нахождении $\Omega(x)$ через $A_r(x)$. Тогда
$$
\Omega_{r+1}(x) = \Omega_r(x) + \Delta r A_r(x),
$$
$$
A_{r+1}(x) = \left\{ 
   \begin{array}{l l}
     x A_r(x), &  L_{r+1} = L_r\\
     x \Omega_r(x)\Delta r^{-1}, &  L_{r+1} > L_r
   \end{array} \right.
$$
Полагаем, что $\Omega_0(x) = 0$ и $A_0(x) = 1$.

\subsubsection{Исправление ошибок и стираний}
Использование стираний упрощает процедуру декодирования, так как для стертого 
символа известно хотя бы его местоположение. Недостатком является расширение 
алфавита принимаемых символов по отношению к переданным.

Если кодовое расстояние кода равно $D$ и принятая комбинация содержит $\mu$ 
ошибочных символов, соответствующих стираниям, то при декодировании $\mu$ 
стёртых символов могут быть игнорированы. При этом две кодовые комбинации 
будут отличаться друг от друга по меньшей мере в $D - \mu$ остальных позициях, 
что позволяет в дополнение к стираниям исправлять 
$\left[ \frac{D - \mu - 1}{2}\right] = \upsilon$ ошибок. Таким образом, 
код может исправлять все комбинации из $\mu$ стираний и $\upsilon$ ошибок в кодовой 
комбинации, если выполняется условие
$$
D > 2\upsilon  + \mu.
$$

Сложность реализации исправления стираний в кодах Рида--Соломона соизмерима 
со сложностью реализации исправления ошибок. По аналогии с исправлением ошибок 
вводится многочлен локаторов стираний
$$
\Gamma(x) = \prod_{k=1}^\mu (1 - xU_k)
$$
Зная места стираний, можно вычислить $\Gamma(x)$ и подставить на эти места 
случайные значения символов. В худшем случае это приведет к появлению $\mu$ 
дополнительных ошибок, местоположение которых известно. 

Ключевое уравнение для случая исправления стираний и ошибок имеет вид 
$$
S(x) \Lambda (x) \Gamma(x) =  \Omega(x) \pmod{x^{2t}}. 
$$
При декодировании необходимо определить $\Gamma(x)$ минимальной степени. 
Предполагая, что при передаче кодовой комбинации по каналу связи в ней появилось 
$\nu$ ошибок, а на стертых позициях добавлено $\mu$ новых ошибок получаем , 
т. е.
$$
\left[S(x) \Lambda(x)\Gamma(x)\right]_{\nu+\mu}^{2t-1}=0.
$$
Это значит, что ключевое уравнение следует рассматривать как систему 
$2t - \nu - \mu$ линейных уравнений для $\nu$ неизвестных коэффициентов $\Lambda$. 
Эта система имеет решение при $2\nu + \mu > 2t$.

После нахождения многочлена $\Lambda$ при решении ключевого уравнения получаем 
многочлен $\Lambda (x) =  \Psi(x)$, представляющий собою общий многочлен локаторов 
ошибок и стираний --- многочлен локаторов искажений и многочлен значений 
ошибок $\Omega(x)$. Затем по процедуре Ченя находим положения ошибок, а по алгоритму 
Форни --- значения ошибок и стираний. При этом в алгоритм Берлекэмпа--Месси, 
приведенный на рисунке \ref{fig:BMDiagram}, необходимо внести следующие изменения: 

1. вычислить $\Gamma(x)$,

2. заменить $\Lambda$ на $\Psi(x)$,

3. вычисление $\Psi(x)$ начать с шага $r =  \deg[\Gamma(x)] =  \mu$ при следующих начальных 
условиях $r =  L =  \mu, B(x) =  \Psi(x) =  \Gamma(x)$,

4. заменить критерий проверки условия, при котором следует увеличить длину 
регистра $2L >  m + r - 1$ и значение изменяемой длины регистра $L <  r + \mu - L$,

5. заменить проверку выполнения условия завершения итераций на $r =  \nu - k$.

Однако данная процедура не позволяет получить многочлен значений ошибок $\Omega(x)$.

Многочлен значений ошибок $\Omega(x)$ 
вычисляется по формуле 
$$
\Omega(x) =  S(x) \Psi(x).
$$

\subsection{\textsc{Общий алгоритм распознавания
двумерных штрихкодов}}

Безусловно, каждый код имеет свои особенности, и для декодирования можно 
использовать различные методы \cite{bib:kruchinin, bib:kruchinin2, bib:vina}. 
Ниже будет описан алгоритм, который 
раскрывает общий подход распознавания матричных штрихкодов.

\begin{enumerate}
\item Необходимо получить растровое изображение области, содержащей 
штрихкод. Это может быть фотоаппарат или сканер, значения не имеет.

\item Изображение бинаризуется (при необходимости). Очень важно, 
чтобы бинарное изображение было максимально чётким, потому не следует
использовать глобальный порог. Следует также помнить, что на этом
этапе ещё не выделена область с кодом, и потому производиться обработка
всего изображения, а значит алгоритм бинаризации должен быть максимально 
эффективным, чтобы не задерживать работу всего алгоритма.

\item В чёрно-белом изображении производиться поиск штрихкода используя
свойственные каждому конкретному коду шаблоны поиска. Результатом
поиска является четырёхугольник, ограничивающий штрихкод, а также
число строк и столбцов в нём. Возможно, на этом этапе дополнительно
потребуется начать частичное декодирование для того,
чтобы получить размер, ибо он необходим для следующего шага.

\item Далее необходимо произвести перспективное преобразование
(см. Рисунок \ref{fig:persTrans}) переводящее
выделенный на предыдущем шаге четырёхугольник в правильно 
сориентированную матрицу барселей двумерного кода. Т.е. производиться
выделение штрихкода без пространственных искажений. Подробнее об этом
можно найти здесь: \cite{bib:wolberg}. См. также 
Приложения c. \pageref{sec:perTransform}.

\item По полученной матрице считывается массив байтов. Определяется
размер сообщения.

\item Производится поиск и коррекция ошибок. 

\item Скорректированный массив преобразуется в нужное представление
(текст, цифры и т.д.).   

\end{enumerate}   

\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.7]{img/pers_trans}
    \caption{Перспективное преобразование}
    \label{fig:persTrans}
\end{figure}

Для сравнения, можно не производить перспективное преобразование, 
а производить 
распознавание прямо на выделенной области, однако это, очевидно, 
сложнее. 